package com.wwlwxg.dataStructure;

import java.util.Arrays;

/**
 * 数组实现的队列，可以自动扩容
 * 队列方法：入队、出队
 * 队列的存储：即队首队尾两个指针，
 * 扩容：如果队列容量不够了，应该扩容，如果队尾没有位置了，队首有位置，应该把元素往前移
 */
public class ScaleArrayQueue {

	// 存储数据的数组
	private Object[] elements;
	//队列大小
	private int size;
	// 默认队列容量
	private static final int DEFAULT_CAPACITY = 10;
	// 队列头指针，消费者
	private int head;
	// 队列尾指针,生产者
	private int tail;

	private int MAX_ARRAY_SIZE  = Integer.MAX_VALUE-8;

	public ScaleArrayQueue() {
		this(DEFAULT_CAPACITY);
	}

	public ScaleArrayQueue(int size) {
		elements = new Object[size];
		initPointer(0, 0);
	}

	public static void main(String[] args) {
		ScaleArrayQueue queue = new ScaleArrayQueue(4);

		//入队列
		queue.add("helius1");
		queue.add("helius2");
		queue.add("helius3");
		queue.add("helius4");
		//此时入队列应该走扩容的逻辑
		queue.add("helius5");
		queue.add("helius6");
		//出队列
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		//此时入队列应该走数据搬移逻辑
		queue.add("helius7");
		//出队列
		System.out.println(queue.poll());
		//入队列
		queue.add("helius8");
		//出队列
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		//入队列
		queue.add("helius9");
		queue.add("helius10");
		queue.add("helius11");
		queue.add("helius12");
		//出队列
		System.out.println(queue.poll());
		System.out.println(queue.poll());
	}

	/**
	 * 入队列
	 */
	public boolean add(Object element) {
		ensureCapacityHelper();
		elements[tail] = element;
		tail++;
		size++;
		return true;
	}

	/**
	 * 初始化队列头尾指针
	 * @param head
	 * @param tail
	 */
	private void initPointer(int head,int tail){
		this.head = head;
		this.tail = tail;
	}

	private void ensureCapacityHelper() {
		if(tail == elements.length) {//尾指针已越过数组尾端
			// 判断队列是否已经满了，满则扩容
			if(head == 0) {
				// 扩容
				grow(elements.length);
			} else {
				//进行数据搬移操作 将数组中的数据依次向前挪动直至顶部
				for(int i = head; i < tail; i++) {
					elements[i - head] = elements[i];
				}
				//数据搬移完后重新初始化头尾指针
				initPointer(0,tail-head);
			}
		}
	}

	/**
	 * 扩容
	 * @param oldCapacity 原始容量
	 */
	private void grow(int oldCapacity) {
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		if(newCapacity - oldCapacity < 0) {
			newCapacity = DEFAULT_CAPACITY;
		}
		if(newCapacity - MAX_ARRAY_SIZE > 0) {
			newCapacity = hugeCapacity(newCapacity);
		}
		elements = Arrays.copyOf(elements, newCapacity);
	}

	private int hugeCapacity(int newCapacity) {
		return (newCapacity - MAX_ARRAY_SIZE > 0 ) ? Integer.MAX_VALUE : newCapacity;
	}

	/**
	 * 出队列
	 * @return
	 */
	public Object poll(){
		if(head==tail){
			return null;//队列中没有数据
		}
		Object obj = elements[head++];//取出队列头的元素且头指针后移
		size--;//队列中元素个数减1
		return obj;
	}

	/**
	 * 获取队列元素个数
	 * @return
	 */
	public int getSize() {
		return size;
	}
}
